package jleda.tree;

public class BinaryHeapMap<K extends Comparable<K>,V> {
	private static final int DEFAULT_SIZE = 8;
	private static final int RESIZE_FACTOR = 2;
	private K[] arrk;
	private V[] arrv;
	private int size;
	
	public BinaryHeapMap() {
		arrk = (K[])new Comparable[DEFAULT_SIZE];
		arrv = (V[])new Object[DEFAULT_SIZE];
		size = 0;
	}
	
	public void insert( K key, V value ) {
		if( size+1 == arrk.length ) {
			K[] t = (K[])new Comparable[RESIZE_FACTOR*arrk.length];
			V[] u = (V[])new Object[RESIZE_FACTOR*arrv.length];
			System.arraycopy( arrk, 1, t, 1, size );
			System.arraycopy( arrv, 1, u, 1, size );
			arrk = t;
			arrv = u;
		}
		
		int hole = ++size;
		
		for( ; hole > 1 && key.compareTo( arrk[hole/2] ) < 0; hole /= 2 ) {
			arrk[hole] = arrk[hole/2];
			arrv[hole] = arrv[hole/2];
		}
		
		arrk[hole] = key;
		arrv[hole] = value;
	}
	
	public K findMinKey() {
		return arrk[1];
	}
	
	public V findMinValue() {
		return arrv[1];
	}
	
	public V deleteMin() {
		V min = arrv[1];
		
		int hole = 1, child;
		K t = arrk[1] = arrk[size];
		V u = arrv[1] = arrv[size];
		
		for( ; 2*hole < size; hole = child ) {
			child = 2*hole;
			
			if( child != size && arrk[child+1].compareTo( arrk[child] ) < 0 ) {
				child++;
			}
			
			if( arrk[child].compareTo( t ) < 0 ) {
				arrk[hole] = arrk[child];
				arrv[hole] = arrv[child];
			} else {
				break;
			}
		}
		
		arrk[hole] = t;
		arrv[hole] = u;
		size--;
		return min;
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
}
